import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class project {
    public int reductionOperations(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);
        int max=nums[len-1];
        if(nums[0]==max){
            return 0;
        }
        int count=0;
        for(int i=len-1;i>=0;i--){
            if(nums[i]<max){
                max=nums[i];
                count+=len-i-1;
            }
        }
        return count;
    }

















    public int countEven(int num) {
        int count=0;
        for(int i=2;i<=num;i++){
            if(test(i)){
                count++;
            }
        }
        return count;
    }
    public boolean test(int index){
        int sum=0;
        while (index!=0){
            sum+=index%10;
            index/=10;
        }
        return sum%2==0;
    }















    public int minimumLengthEncoding(String[] words) {
        Set<String> set=new HashSet<>(Arrays.asList(words));
        for(String word:words){
            for(int i=1;i<word.length();i++){
                set.remove(word.substring(i));
            }
        }
        int ret=0;
        for(String s:set){
            ret+=s.length()+1;
        }
        return ret;
    }















    public int mctFromLeafValues(int[] arr) {
        Stack<Integer> stack=new Stack<>();
        stack.add(Integer.MAX_VALUE);
        int ret=0;
        for(int i=0;i<arr.length;i++){
            while (arr[i]>=stack.peek()){
                ret+=stack.pop()*Math.min(stack.peek(),arr[i]);
            }
            stack.add(arr[i]);
        }
        while (stack.size()>2){
            ret+=stack.pop()*stack.pop();
        }
        return ret;
    }

















    int[] left;
    int[] right;
    long max;
    int len;
    int count;
    public int countHighestScoreNodes(int[] parents) {
        len=parents.length;
        max=0;
        count=0;
        left=new int[len];
        right=new int[len];
        Arrays.fill(left,-1);
        Arrays.fill(right,-1);
        for(int i=1;i<len;i++){
            if(left[parents[i]]==-1){
                left[parents[i]]=i;
            }else {
                right[parents[i]]=i;
            }
        }
        dfs(0);
        return count;
    }
    public long dfs(int node){
        if(node==-1){
            return 0;
        }
        long leftLen=dfs(left[node]);
        long rightLen=dfs(right[node]);
        long score=Math.max(leftLen,1)*Math.max(rightLen,1)*Math.max(len-leftLen-rightLen-1,1);
        if(score==max){
            count++;
        }else if(score>max){
            max=score;
            count=1;
        }
        return leftLen+rightLen+1;
    }
}
